Non-volatile data storage devices, such as universal serial bus (USB) flash memory devices or removable storage cards, have allowed for increased portability of data and software applications. Flash memory devices can enhance data storage density by storing multiple bits in each flash memory cell. For example, Multi-Level Cell (MLC) flash memory devices provide increased storage density by storing 3 bits per cell, 4 bits per cell, or more. Although increasing the number of bits per cell and reducing device feature dimensions may increase a storage density of a memory device, a bit error rate of data stored at the memory device may also increase.
Error correction coding (ECC) is often used to correct errors that occur in data read from a memory device. Prior to storage, data may be encoded by an ECC encoder to generate redundant information (e.g. “parity bits”) that may be stored with the data as an ECC codeword. Low-density parity-check (LDPC) ECC codes are adopted in numerous data storage and digital communication systems. These codes can be decoded using different algorithms and scheduling schemes that have various error-correcting performance and implementation costs.
In LDPC decoding, reliability messages are passed between check nodes and variable nodes iteratively until convergence is achieved and the decoded word is error-free. Compared to a traditional flooding scheduling scheme, layered schemes can achieve around twice the convergence speed by updating each message multiple times in a decoding iteration. Additionally, column-layered schemes are more suitable than row-layered schemes for high-speed applications because column-layered schemes process all check nodes simultaneously. However, complex hardware for generation of the updated messages for column-layered schemes increases design and manufacturing costs.
Conventional column-layered schemes are typically designed for a Min-sum decoding algorithm. Although such column-layered schemes tend to converge faster than flooding schemes and can achieve higher throughput than row-layered schemes, updating of messages uses at least three values for each row of the parity check matrix H, including a min1 (first minimum) value, a min2 (second minimum) value, and the index of the min1 value. Storing these values requires a relatively large amount of memory. Moreover, approximations that are used to update messages using only min1, min2, and the index of min1 for each row result in error-correcting performance losses, and additional values, such as a min3 (third minimum) value, are typically needed to mitigate such performance loss.
In order to achieve satisfactory error-correcting performance and not to have early error floor, the Min-sum algorithm usually requires 4-7 bits to represent each message. Using 4-7 bit messages requires use of relatively expensive components such as integer adders, comparators, and converters to implement the check and variable node processing steps of the decoding, resulting in increased manufacturing cost.